package com.copa.l57;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-05-13 16:53
 * @function 贪心法
 */
public class Test2 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        LinkedList<int[]> result = new LinkedList<>();
        int index = 0;
        // 先加入intervals数组里的第一个数比netInterval[0]小的
        for (int[] interval : intervals) {
            if (newInterval[0] > interval[0]) {
                result.add(interval);
                index++;
            } else {
                break;
            }
        }
        // 解决newInterval插入的问题
        if (result.size() == 0 || newInterval[0] > result.getLast()[1]) {
            result.add(newInterval);
        } else {
            result.getLast()[1] = Math.max(result.getLast()[1], newInterval[1]);
        }
        // 加入intervals数组剩下的
        for (int i = index; i < intervals.length; i++) {
            if (intervals[i][0] > result.getLast()[1]) {
                result.add(intervals[i]);
            } else {
                result.getLast()[1] = Math.max(result.getLast()[1], intervals[i][1]);
            }
        }
        return result.toArray(new int[result.size()][2]);
    }

    public static void main(String[] args) {
//        int[][] intervals = new int[][]{{1,2},{3,5},{6,7},{8,10},{12,16}};
//        int[] newInterval = new int[]{4,8};
        int[][] intervals = new int[][]{{1,5}};
        int[] newInterval = new int[]{2,3};
        for (int[] result : new Test2().insert(intervals, newInterval)) {
            System.out.print(Arrays.toString(result) + "\t");
        }
    }
}
